package 动态规划;

public class robotWalk {
	public static void main(String []args) {
		// 机器人 版本一
//		System.out.println(robot(3,7));
//		System.out.println(dp(3,7));
		// 机器人版本 二
		int [][]obstacleGrid = {{0,0,0},{0,1,0},{0,0,0}};
		System.out.println(robot2(obstacleGrid));
		System.out.println(dp(obstacleGrid));
		
	}
	public static int dp(int m,int n) {
		int [][]dp =new int [m+1][n+1];
		dp[m-1][n-1]=1;
		for(int right=n-1;right >=0;right-- ) {
			for(int down = m-1; down>=0 ;down--) {
				if(right==n-1 && down==m-1) {
					continue;
				}
				dp[down][right]=dp[down+1][right]+dp[down][right+1];
			}
		}
		for(int a[] :dp) {
			for(int i: a) {
				System.out.print(i+"   ");
			}
			System.out.println();
		}
		System.out.println(dp[2][6]);
		return dp[0][0];
	}
	public static int robot(int m,int n) {
		return process(0,0,m-1,n-1);
	}
	public static int process(int right,int down,int m,int n) {
		if(right== n && down == m) {
			return 1;
		}
		if(right > n || down > m) {
			return 0;
		}
		// 下面的 递归 也可以 编程枚举  for循环的形式
		return process(right+1,down,m,n)+ process(right,down+1,m,n);
	}
	//  机器人 走 方格 版本  二;
	//dp 方式
	public static int dp(int arr[][]) {
		int m=arr.length;
		int n= arr[0].length;
		// 整个  小加速
		if(arr[m-1][n-1]==1 || arr[0][0]==1) {
			return 0;
		}
		int dp[][] =new int [m+1][n+1];
		dp[m-1][n-1]=1;
		// 下面这一步 就不用设置了啊  对吧  因为是 0  默认就是 零 对吧
//		if(obstacle[right][down]==1) {
//			return  0;
//		}
		for(int right=n-1;right>=0;right--) {
			for(int down =m-1;down >=0; down--) {
				if( (right==n-1 && down==m-1)) {
					continue;
				}
				if(arr[down][right] == 1) {
					dp[down][right]=0;
				}
				else
				dp[down][right]=dp[down+1][right] + dp[down][right+1];
			}
		}
//		for(int a[]: dp) {
//			for(int i: a)
//				System.out.print(i+" ");
//			System.out.println();
//		}
		
		return dp[0][0];
	}
	
	// 暴力递归
	public static int robot2(int arr[][]) {
		int m=arr.length;
		int n= arr[0].length;
		return process1(0,0,m-1,n-1,arr);
	}
	//  这种思想  卧槽  就是 牛逼   说实话
	public static int process1(int right,int down,int m,int n,int obstacle [][]) {
		if(right== n && down == m) {
			return 1;
		}
		if(right > n || down > m) {
			return 0;
		}
		// 最关键的 一 步  就是 这里  我靠 
		if(obstacle[right][down]==1) {
			return  0;
		}
		return process1(right+1,down,m,n,obstacle)+process1(right,down+1,m,n,obstacle);
//		int ways=0;
//		if( down+1<=m&& obstacle[down+1][right] == 1 ) {
//			ways+=process1(right+1,down,m,n,obstacle);
//		}
//		else
//			ways+=process1(right,down+1,m,n,obstacle);
//		if( right+1<=n &&obstacle[down][right+1] == 1) {
//			ways+=process1(right,down+1,m,n,obstacle);
//		}
//		else
//			ways+=process1(right+1,down,m,n,obstacle);
//		return ways;
	}
}
